package likou.dongtaiguihua;
/**
描述

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第 n个丑数。

数据范围：0≤n≤20000≤n≤2000
要求：空间复杂度 O(n) 时间复杂度 O(n)
示例1
输入：
7
返回值：
8
*/

public class 丑数 {
    public static void main(String[] args) {
        System.out.println(GetUglyNumber_Solution(8));
    }
    public static int GetUglyNumber_Solution(int n) {
        int p2=1;
        int p3=1;
        int p5=1;
        int [] dp=new int[n+1];
        dp[1]=1;
        for(int i= 2;i<=n;i++){
            dp[i]=Math.min(Math.min(2*dp[p2],3*dp[p3]),5*dp[p5]);
            if(dp[i]==dp[p2]*2) {
                p2++;
            }
            if(dp[i]==dp[p3]*3) {
                p3++;
            }
            if(dp[i]==dp[p5]*5) {
                p5++;
            }
        }
        return dp[n];

    }
}
